package bTree.LeetCode;

import java.util.*;

public class O1时间插入删除和获取随机元素 {
    HashMap<Integer,Integer>hashMap;
    List<Integer> list;

    public O1时间插入删除和获取随机元素() {
        this.hashMap=new HashMap<>();
        this.list = new ArrayList<>();
    }

    public boolean insert(int val) {
        if (!hashMap.containsKey(val)) {
            hashMap.put(val,list.size());
            list.add(val);
            return true;
        }
        return false;
    }

    public boolean remove(int val) {
        if (hashMap.containsKey(val)){
            int index=hashMap.get(val);
            if(index==list.size()-1){
                list.remove(list.size()-1);
                hashMap.remove(val);
                return true;
            }
            int value=list.get(list.size()-1);
            list.set(index,value);
            list.remove(list.size()-1);
            hashMap.remove(val);
            hashMap.put(value,index);
            return true;
        }
        return false;
    }

    public int getRandom() {
        Random random=new Random();
        return list.get(random.nextInt(list.size()));
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */